package greedy;

/**
 * Created with IntelliJ IDEA.
 * Description: 134. 加油站
 * User: Li_yizYa
 * Date: 2025/6/26
 * Time: 12:28
 */
public class Solution8 {
    /**
     * 站在全局角度考虑问题
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
            return -1;
        }
        int curSum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < cost.length; i++) {
            curSum += gas[i] - cost[i];
            min = Math.min(min, curSum);
        }
        if (curSum < 0) {
            return -1;
        }
        if (min >= 0) {
            return 0;
        }
        for (int i = cost.length - 1; i >= 0; i--) {
            min += gas[i] - cost[i];
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 局部最优推全局最优
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
            return -1;
        }
        int start = 0;
        int curSum = 0;
        int totalSum = 0;
        for (int i = 0; i < cost.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                curSum = 0;
                start = i + 1;
            }
        }
        if (totalSum < 0) {
            return -1;
        }
        return start;
    }
    /**
     * 暴力解法
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
            return -1;
        }
        for (int i = 0; i < cost.length; i++) {
            int rest = gas[i] - cost[i];
            int index = (i + 1) % cost.length;
            while (rest >= 0 && index != i) {
                rest += (gas[index] - cost[index]);
                index = (index + 1) % cost.length;
            }
            if (rest >= 0 && index == i) {
                return i;
            }
        }
        return -1;
    }
}
